#include "graph_support/alg_correctness_tests/dinic_alg_tests/CompactNetDinic.h"

#include <assert.h>

#include "graph_support/alg_correctness_tests/dinic_alg_tests/CompactNet.h"

using namespace dinic_alg_test;

namespace
{

bool bfs( CompactNet & gr, int src, int dest, int * edge2parent, double eps )
{
	int vertCount = gr.getVertCount();
	std::fill( edge2parent, edge2parent + vertCount, -1 );
	char NEW = 0;
	char QUEUED = 1;
	char COMPLETED = 2;
	std::vector< char > stateBuf( vertCount );
	char * state = & stateBuf[0];
	std::fill( state, state + vertCount, NEW );
	std::vector< int > queueBuf( vertCount );
	int * head = & queueBuf[0];
	int * tail = head;
	int * tailLim = tail + vertCount;
	assert( tail < tailLim );
	* tail = src;
	state[src] = QUEUED;
	tail++;
	while ( head < tail && state[dest] == NEW )
	{
		int v = * head;
		head++;
		for ( int j = gr.st[v]; j > -1; j = gr.nx[j] )
		{
			int d = gr.a[j];
			if ( state[d] != NEW )
			{
				continue;
			}
			double r = gr.remainFlow( j );
			if ( r < eps )
			{
				continue;
			}
			assert( tail < tailLim );
			state[d] = QUEUED;
			edge2parent[d] = j;
			* tail = d;
			tail++;
		}
		state[v] = COMPLETED;
	}
	return state[dest] != NEW;
}

double pushFlow( CompactNet & gr, int src, int dest, int * edge2parent )
{
	double eps = 1e-5;
	std::vector< int > d2sBuf;
	d2sBuf.reserve( gr.getVertCount() );
	{
	int v = dest;
	while ( v != src )
	{
		int j = edge2parent[v];
		assert( gr.a[j] == v );
		v = gr.a[j ^ 1];
		d2sBuf.push_back( j );
	}
	}
	int n = d2sBuf.size();
	int * d2s = & d2sBuf[0];
	double minrem = 1e30;
	for ( int i = 0; i < n; i++ )
	{
		int j = d2s[i];
		double r = gr.remainFlow( j );
		minrem = std::min( minrem, r );
	}
	for ( int i = 0; i < n; i++ )
	{
		int j = d2s[i];
		gr.flow[j] += minrem;
		assert( gr.flow[j] < gr.cap[j] + eps );
		gr.flow[j ^ 1] -= minrem;
	}
	return minrem;
}

void eraseFlow( CompactNet & gr )
{
	int n = gr.getVertCount();
	for ( int i = 0; i < n; i++ )
	{
		for ( int j = gr.st[i]; j > -1; j = gr.nx[j] )
		{
			gr.flow[j] = 0;
		}
	}
}

}

double dinic_alg_test::stupidDinicOnCompactNet(
		dinic_alg_test::CompactNet & gr,
		int src, int dest,
		double eps
) {
	eraseFlow( gr );
	// TODO: common notation: n, vertexCount
	int vertCount = gr.getVertCount();
	int edgCount = gr.getEdgCount();
	std::vector< int > edge2parentBuf( vertCount );
	int * edge2parent = & edge2parentBuf[0];
	double totalFlow = 0;
	while ( bfs( gr, src, dest, edge2parent, eps ) )
	{
		assert( edge2parent[dest] > -1 );
		double pushed = pushFlow( gr, src, dest, edge2parent );
		assert( pushed > eps );
		totalFlow += pushed;
	}
	return totalFlow;
}

// TODO: separate Dinic and min cost flow OR rename
namespace
{

typedef int FordBellmanResult;
FordBellmanResult const FORD_BELLMAN_RESULT_PATH_FOUND = -1;
FordBellmanResult const FORD_BELLMAN_RESULT_DEST_IS_UNREACHABLE = -2;
FordBellmanResult const FORD_BELLMAN_NEGATIVE_CYCLE_FOUND__BEG = 0;

FordBellmanResult runFordBellman( CompactNet & gr, int src, int dest, int * edgeFromParent, double eps = 1e-5, double inf = 1e30 )
{
	int n = gr.getVertCount();
	std::vector< double > distBuf( n, inf );
	double * dist = & distBuf[0];
	std::fill( edgeFromParent, edgeFromParent + n, -1 );

	dist[src] = 0;
	bool updated;
	int iterationCounter = 0;
	bool negativeCycleFound = false;
	int lastUpdated = -1;
	do
	{
		updated = false;
		for ( int i = 0; i < n; i++ )
		{
			for ( int j = gr.st[i]; j > -1; j = gr.nx[j] )
			{
				if ( gr.remainFlow( j ) < eps )
				{
					continue;
				}
				int d = gr.a[j];
				double updDist = dist[i] + gr.cost[j];
				if ( dist[i] == inf )
				{
					updDist = inf;
				}
				if ( dist[d] > updDist + eps )
				{
					dist[d] = updDist;
					edgeFromParent[d] = j;
					updated = true;
					lastUpdated = d;
				}
			}
		}
		iterationCounter++;
		if ( iterationCounter > n )
		{
			negativeCycleFound = true;
			break;
		}
	} while ( updated );

	if ( negativeCycleFound )
	{
		int negativeCyclePart = lastUpdated;
		assert( lastUpdated >= FORD_BELLMAN_NEGATIVE_CYCLE_FOUND__BEG );
		return negativeCyclePart;
	}
	return dist[dest] < inf ?
			FORD_BELLMAN_RESULT_PATH_FOUND :
			FORD_BELLMAN_RESULT_DEST_IS_UNREACHABLE;
}

std::pair< double, double > pushFlowThroPath( CompactNet & gr, int start, int finish, double desiredFlow, int * edgeFromParent, double eps = 1e-5 )
{
	double minCap = desiredFlow;
	int i = finish;
	int n = gr.getVertCount();
	std::vector< char > visitedBuf(n, ( char ) false );
	bool * visited = ( bool * ) & visitedBuf[0];
	do
	{
		assert( ! visited[i] );
		visited[i] = true;
		int j = edgeFromParent[i];
		assert( i == gr.a[j] );// TODO: check the same in official MinCostFlow
		double remainCap = gr.remainFlow( j );
		if ( minCap > remainCap )
		{
			minCap = remainCap;
		}
		int jr = j ^ 1;
		i = gr.a[jr];
	} while ( i != start );

	i = finish;
	double cost = 0;
	do
	{
		int j = edgeFromParent[i];
		int jr = j ^ 1;
		gr.flow[j] += minCap;
		assert( gr.flow[j] <= gr.cap[j] + eps );
		gr.flow[jr] -= minCap;
		assert( gr.flow[jr] <= gr.cap[jr] + eps );
		cost += gr.cost[j] * minCap;
		i = gr.a[jr];
	} while ( i != start );
	return std::pair< double, double >( start == finish ? 0 : minCap, cost );
}

int discoverNegativeCyclePart( CompactNet & gr, int negativeCycleChild, int * edgeFromParent )
{
	int n = gr.getVertCount();
	std::vector< char > visitedBuf( n, ( char ) false );
	bool * visited = ( bool * ) & visitedBuf[0];
	int i = negativeCycleChild;
	while ( ! visited[i] )
	{
		visited[i] = true;
		int j = edgeFromParent[i];
		assert( gr.a[j] == i );
		int jr = j ^ 1;
		i = gr.a[jr];
	}
	assert( visited[i] );
	return i;
}

}

std::pair< double, double > dinic_alg_test::stupidMinCostFlowOnCompactNet(
		dinic_alg_test::CompactNet & gr,
		int src, int dest,
		double desiredFlow,
		double eps
) {
	assert( gr.cost != NULL );
	eraseFlow( gr );
	int n = gr.getVertCount();
	double totalFlow = 0;
	double totalCost = 0;
	std::vector< int > edgeFromParentBuf( n, -1 );
	int * edgeFromParent = & edgeFromParentBuf[0];
	while ( totalFlow < desiredFlow - eps )
	{
		FordBellmanResult fbResult = runFordBellman( gr, src, dest, edgeFromParent );
		bool pushFlowPathFound = fbResult == FORD_BELLMAN_RESULT_PATH_FOUND;
		bool negativeCycleFound = fbResult >= FORD_BELLMAN_NEGATIVE_CYCLE_FOUND__BEG;
		std::pair< double, double > pushResult;
		if ( pushFlowPathFound )
		{
			pushResult = pushFlowThroPath( gr, src, dest, desiredFlow - totalFlow, edgeFromParent );
		} else
		if ( negativeCycleFound )
		{
			int negativeCycleChild = fbResult;
			int negativeCyclePart = discoverNegativeCyclePart( gr, negativeCycleChild, edgeFromParent );
			pushResult = pushFlowThroPath( gr, negativeCyclePart, negativeCyclePart, desiredFlow - totalFlow, edgeFromParent );
		} else
		{
			assert( fbResult == FORD_BELLMAN_RESULT_DEST_IS_UNREACHABLE );
			break;
		}
		totalFlow += pushResult.first;
		totalCost += pushResult.second;
	}
	return std::pair< double, double >( totalFlow, totalCost );
}
